今天的題單：

• Number of 1 Bits

• Longest Common Prefix

191. Number of 1 Bits

這題跟 338. Counting Bits 算是重複，都是在求正整數換成二進位表示有幾個 1。
在上一篇已經寫過怎麼實作了，這次來講一些 C++ 相關小知識。
先上之前使用過的 built-in function：

class Solution {
public:
    int hammingWeight(int n) {
        return __builtin_popcount(n);
    }
};

其實在 C++ 20 後 popcount 有進入 standard library (std::popcount)，一樣是計算 unsigned integer 有幾個 1，但是參數必須直接是 unsigned：

class Solution {
public:
    int hammingWeight(int n) {
        return popcount(static_cast<unsigned int>(n));
    }
};

__builtin_popcount() 和 std::popcount 差在哪裡?

首先這兩個的來源是不同的，一個是 built-in function，一個是標準函式庫。

built-in function 是指 complier 的內建函式，他可能會直接對應到一組指令或軟體實作。簡單來說，它是 compiler 幫忙做好的一個功能，並不在標準函式庫內。

__builtin_popcount() 能夠對應到 x86 的 POPCNT 指令

使用 built-in function 的優點是可以透過 compiler 對應到最佳或效率更好的硬體或軟體實作，但缺點是程式的可攜性差，如果 compiler 不支援這個 built-in function，就會無法編譯 (code 就要重寫)。

而 std::popcount 是標準函式庫的一部份。它的好處是只要是支援 C++ 20 的 compiler 都能夠編譯使用 std::popcount 的程式。而具體的實作要看標準函式庫如何實作 (例如 GCC 的 libstdc++ 或 Clang 的 libc++)，所以 compiler 也可能會選擇去呼叫自己的 built-in function。

因此使用這類函式需要注意自己使用的 compiler 以及使用 C++ 標準。

14. Longest Common Prefix

思路: 暴力法，loop 整個 vector string 一個字一個字看

題目的 prefix 指的是從 string 的開頭開始算。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        char c;
        int index = 0;
        string common_prefix;

        while (true) {
            bool all_same = true;
            c = strs[0][index];
            for (string& str : strs) {
                if (index >= str.size()) {
                    all_same = false;
                    break;
                }
                if (str[index] != c) {
                    all_same = false;
                    break;
                }
            }

            if (all_same) {
                common_prefix = common_prefix + c;
            } else {
                break;
            }

            index ++;
            all_same = true;
        }

        return common_prefix;
    }
};